package crawler.web.deduplicate;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author waynechen Mar 17, 2012 3:00:10 PM
 */
public class SimHashUtil {
	/**
	 * 计算相似的simHash值
	 * 
	 * @author waynechen
	 * @param fingerPrint
	 * @param k
	 * @return
	 */
	public static List<Long> getSimHashList(long fingerPrint, int k) {
		List<Long> retAll = new LinkedList<Long>();
		for (int ki = 1; ki <= k; ++ki) {
			CombinationGenerator x = new CombinationGenerator(64, ki);
			while (x.hasMore()) {
				int[] indices = x.getNext();
				long simFP = fingerPrint;
				for (int i = 0; i < indices.length; i++) {
					simFP = simFP ^ 1L << indices[i];
				}
				retAll.add(simFP);
			}
		}
		return retAll;
	}

	/**
	 * 计算simHash
	 * 
	 * @author waynechen
	 * @param list
	 * @param weights
	 * @return
	 */
	public static long getSimHash(List<String> list) {
		Integer[] ws = new Integer[list.size()];
		for (int i = 0, j = list.size(); i < list.size(); i++, j--)
			ws[i] = j * 3;
		List<Integer> weights = Arrays.asList(ws);
		return getSimHash(list, weights);
	}

	/**
	 * 计算simHash
	 * 
	 * @author waynechen
	 * @param list
	 * @param weights
	 * @return
	 */
	public static long getSimHash(List<String> list, List<Integer> weights) {
		int[] histogram = new int[64];//创建直方图
		for (int i = 0; i < list.size(); i++) {
			long addressHash = GeneralHashFunctionLibrary.DJBHash(list.get(i));
			int weight = weights.get(i);
			for (int c = 0; c < 64; c++) {
				long tmp = addressHash & (1 << c);
				//更新histogram的第c位
				histogram[c] += tmp == 0 ? -weight : weight;
			}
		}
		long simHash = 0;
		for (int c = 0; c < 64; c++) {
			long t = (histogram[c] >= 0) ? 1 : 0;
			t <<= c;
			simHash |= t;
		}
		return simHash;
	}

	/**
	 * 计算海明距离
	 * 
	 * @author waynechen
	 * @param a
	 * @param b
	 * @return
	 */
	public static int hammingDistance(long a, long b) {
		long c = a ^ b;
		return BitUtil.pop(c);
	}

}

//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//